<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>分类: 面试 | 小小程序员</title><meta name="author" content="十一星野"><meta name="copyright" content="十一星野"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="本文由 简悦 SimpRead 转码， 原文地址 javaguide.cn   JavaGuide 官方知识星球 Map（重要） HashMap 和 Hashtable 的区别 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的, 因为 Hashtable 内部的方法基本都经过 synchronized 修饰。  # Map（重要）# HashMap 和 Hasht">
<meta property="og:type" content="article">
<meta property="og:title" content="Java集合常见面试题总结(下)">
<meta property="og:url" content="https://ko25891wan.gitlab.io/2024/01/fd03bd589630.html">
<meta property="og:site_name" content="小小程序员">
<meta property="og:description" content="本文由 简悦 SimpRead 转码， 原文地址 javaguide.cn   JavaGuide 官方知识星球 Map（重要） HashMap 和 Hashtable 的区别 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的, 因为 Hashtable 内部的方法基本都经过 synchronized 修饰。  # Map（重要）# HashMap 和 Hasht">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/%E5%A4%B4%E5%83%8F/%E7%81%B0%E5%A4%AA%E7%8B%BC.png">
<meta property="article:published_time" content="2024-01-31T06:55:47.000Z">
<meta property="article:modified_time" content="2024-02-03T04:45:44.581Z">
<meta property="article:author" content="十一星野">
<meta property="article:tag" content="宅男,热血">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/%E5%A4%B4%E5%83%8F/%E7%81%B0%E5%A4%AA%E7%8B%BC.png"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://ko25891wan.gitlab.io/2024/01/fd03bd589630.html"><link rel="preconnect" href="//fastly.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.5.1/css/all.min.css"><link rel="stylesheet" href="https://cdn.staticfile.org/fancyapps-ui/5.0.32/fancybox/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
  root: '/',
  algolia: undefined,
  localSearch: {"path":"/search.xml","preload":false,"top_n_per_article":1,"unescape":false,"languages":{"hits_empty":"找不到您查询的内容：${query}","hits_stats":"共找到 ${hits} 篇文章"}},
  translate: {"defaultEncoding":1,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":200},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: true,
    post: true
  },
  runtime: '',
  dateSuffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  infinitegrid: {
    js: 'https://cdn.staticfile.org/egjs-infinitegrid/4.11.0/infinitegrid.min.js',
    buttonText: '加载更多'
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false,
  percent: {
    toc: true,
    rightside: true,
  },
  autoDarkmode: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '分类: 面试',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2024-02-03 12:45:44'
}</script><script>(win=>{
      win.saveToLocal = {
        set: (key, value, ttl) => {
          if (ttl === 0) return
          const now = Date.now()
          const expiry = now + ttl * 86400000
          const item = {
            value,
            expiry
          }
          localStorage.setItem(key, JSON.stringify(item))
        },
      
        get: key => {
          const itemStr = localStorage.getItem(key)
      
          if (!itemStr) {
            return undefined
          }
          const item = JSON.parse(itemStr)
          const now = Date.now()
      
          if (now > item.expiry) {
            localStorage.removeItem(key)
            return undefined
          }
          return item.value
        }
      }
    
      win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
        const script = document.createElement('script')
        script.src = url
        script.async = true
        script.onerror = reject
        script.onload = script.onreadystatechange = function() {
          const loadState = this.readyState
          if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
          script.onload = script.onreadystatechange = null
          resolve()
        }

        Object.keys(attr).forEach(key => {
          script.setAttribute(key, attr[key])
        })

        document.head.appendChild(script)
      })
    
      win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
        const link = document.createElement('link')
        link.rel = 'stylesheet'
        link.href = url
        if (id) link.id = id
        link.onerror = reject
        link.onload = link.onreadystatechange = function() {
          const loadState = this.readyState
          if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
          link.onload = link.onreadystatechange = null
          resolve()
        }
        document.head.appendChild(link)
      })
    
      win.activateDarkMode = () => {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = () => {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
        if (t === 'dark') activateDarkMode()
        else if (t === 'light') activateLightMode()
      
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
      const detectApple = () => {
        if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
          document.documentElement.classList.add('apple')
        }
      }
      detectApple()
    })(window)</script><meta name="generator" content="Hexo 6.3.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><script>(()=>{
  const $loadingBox = document.getElementById('loading-box')
  const $body = document.body
  const preloader = {
    endLoading: () => {
      $body.style.overflow = ''
      $loadingBox.classList.add('loaded')
    },
    initLoading: () => {
      $body.style.overflow = 'hidden'
      $loadingBox.classList.remove('loaded')
    }
  }

  preloader.initLoading()
  window.addEventListener('load',() => { preloader.endLoading() })

  if (false) {
    document.addEventListener('pjax:send', () => { preloader.initLoading() })
    document.addEventListener('pjax:complete', () => { preloader.endLoading() })
  }
})()</script><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/%E5%A4%B4%E5%83%8F/%E7%81%B0%E5%A4%AA%E7%8B%BC.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">120</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">4</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">22</div></a></div><hr class="custom-hr"/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-tools"></i><span> 工具</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/md_editor/"><i class="fa-fw fas fa-pen"></i><span> MDEditor_my</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="not-top-img" id="page-header"><nav id="nav"><span id="blog-info"><a href="/" title="小小程序员"><span class="site-name">小小程序员</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-tools"></i><span> 工具</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/md_editor/"><i class="fa-fw fas fa-pen"></i><span> MDEditor_my</span></a></li></ul></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav></header><main class="layout" id="content-inner"><div id="post"><div id="post-info"><h1 class="post-title">Java集合常见面试题总结(下)</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2024-01-31T06:55:47.000Z" title="发表于 2024-01-31 14:55:47">2024-01-31</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2024-02-03T04:45:44.581Z" title="更新于 2024-02-03 12:45:44">2024-02-03</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E9%9D%A2%E8%AF%95/">面试</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E9%9D%A2%E8%AF%95/%E9%9D%A2%E8%AF%95%E5%AE%9D%E5%85%B8/">面试宝典</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">7.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>26分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="Java集合常见面试题总结(下)"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div><article class="post-content" id="article-container"><blockquote>
<p>本文由 <a target="_blank" rel="noopener" href="http://ksria.com/simpread/">简悦 SimpRead</a> 转码， 原文地址 <a target="_blank" rel="noopener" href="https://javaguide.cn/java/collection/java-collection-questions-02.html#%E5%90%8C%E6%AD%A5%E6%8E%A7%E5%88%B6">javaguide.cn</a></p>
</blockquote>
<blockquote>
<p>JavaGuide 官方知识星球 Map（重要） HashMap 和 Hashtable 的区别 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的, 因为 Hashtable 内部的方法基本都经过 synchronized 修饰。</p>
</blockquote>
<h2 id="Map（重要）"><a href="#Map（重要）" class="headerlink" title="# Map（重要）"></a><a href="#map-%E9%87%8D%E8%A6%81">#</a> Map（重要）</h2><h3 id="HashMap-和-Hashtable-的区别"><a href="#HashMap-和-Hashtable-的区别" class="headerlink" title="# HashMap 和 Hashtable 的区别"></a><a href="#hashmap-%E5%92%8C-hashtable-%E7%9A%84%E5%8C%BA%E5%88%AB">#</a> HashMap 和 Hashtable 的区别</h3><ul>
<li><strong>线程是否安全：</strong> <code>HashMap</code> 是非线程安全的，<code>Hashtable</code> 是线程安全的, 因为 <code>Hashtable</code> 内部的方法基本都经过 <code>synchronized</code> 修饰。（如果你要保证线程安全的话就使用 <code>ConcurrentHashMap</code> 吧！）；</li>
<li><strong>效率：</strong> 因为线程安全的问题，<code>HashMap</code> 要比 <code>Hashtable</code> 效率高一点。另外，<code>Hashtable</code> 基本被淘汰，不要在代码中使用它；</li>
<li><strong>对 Null key 和 Null value 的支持：</strong> <code>HashMap</code> 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 <code>NullPointerException</code>。</li>
<li><strong>初始容量大小和每次扩充容量大小的不同：</strong> ① 创建时如果不指定容量初始值，<code>Hashtable</code> 默认的初始大小为 11，之后每次扩充，容量变为原来的 2 n+1。<code>HashMap</code> 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 <code>Hashtable</code> 会直接使用你给定的大小，而 <code>HashMap</code> 会将其扩充为 2 的幂次方大小（<code>HashMap</code> 中的 <code>tableSizeFor()</code> 方法保证，下面给出了源代码）。也就是说 <code>HashMap</code> 总是使用 2 的幂作为哈希表的大小, 后面会介绍到为什么是 2 的幂次方。</li>
<li><strong>底层数据结构：</strong> JDK 1.8 以后的 <code>HashMap</code> 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。<code>Hashtable</code> 没有这样的机制。</li>
</ul>
<p><strong><code>HashMap</code> 中带有初始容量的构造函数：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">public HashMap(int initialCapacity, float loadFactor) &#123;</span><br><span class="line">        if (initialCapacity &lt; 0)</span><br><span class="line">            throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; +</span><br><span class="line">                                               initialCapacity);</span><br><span class="line">        if (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">            initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">        if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))</span><br><span class="line">            throw new IllegalArgumentException(&quot;Illegal load factor: &quot; +</span><br><span class="line">                                               loadFactor);</span><br><span class="line">        this.loadFactor = loadFactor;</span><br><span class="line">        this.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">    &#125;</span><br><span class="line">     public HashMap(int initialCapacity) &#123;</span><br><span class="line">        this(initialCapacity, DEFAULT_LOAD_FACTOR);</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>下面这个方法保证了 <code>HashMap</code> 总是使用 2 的幂作为哈希表的大小。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line">     * Returns a power of two size for the given target capacity.</span><br><span class="line">     */</span><br><span class="line">    static final int tableSizeFor(int cap) &#123;</span><br><span class="line">        int n = cap - 1;</span><br><span class="line">        n |= n &gt;&gt;&gt; 1;</span><br><span class="line">        n |= n &gt;&gt;&gt; 2;</span><br><span class="line">        n |= n &gt;&gt;&gt; 4;</span><br><span class="line">        n |= n &gt;&gt;&gt; 8;</span><br><span class="line">        n |= n &gt;&gt;&gt; 16;</span><br><span class="line">        return (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<h3 id="HashMap-和-HashSet-区别"><a href="#HashMap-和-HashSet-区别" class="headerlink" title="# HashMap 和 HashSet 区别"></a><a href="#hashmap-%E5%92%8C-hashset-%E5%8C%BA%E5%88%AB">#</a> HashMap 和 HashSet 区别</h3><p>如果你看过 <code>HashSet</code> 源码的话就应该知道：<code>HashSet</code> 底层就是基于 <code>HashMap</code> 实现的。（<code>HashSet</code> 的源码非常非常少，因为除了 <code>clone()</code>、<code>writeObject()</code>、<code>readObject()</code> 是 <code>HashSet</code> 自己不得不实现之外，其他方法都是直接调用 <code>HashMap</code> 中的方法。</p>
<table><thead><tr><th><code>HashMap</code></th><th><code>HashSet</code></th></tr></thead><tbody><tr><td>实现了 <code>Map</code> 接口</td><td>实现 <code>Set</code> 接口</td></tr><tr><td>存储键值对</td><td>仅存储对象</td></tr><tr><td>调用 <code>put ()</code>向 map 中添加元素</td><td>调用 <code>add ()</code>方法向 <code>Set</code> 中添加元素</td></tr><tr><td><code>HashMap</code> 使用键（Key）计算 <code>hashcode</code></td><td><code>HashSet</code> 使用成员对象来计算 <code>hashcode</code> 值，对于两个对象来说 <code>hashcode</code> 可能相同，所以<code>equals ()</code>方法用来判断对象的相等性</td></tr></tbody></table>

<h3 id="HashMap-和-TreeMap-区别"><a href="#HashMap-和-TreeMap-区别" class="headerlink" title="# HashMap 和 TreeMap 区别"></a><a href="#hashmap-%E5%92%8C-treemap-%E5%8C%BA%E5%88%AB">#</a> HashMap 和 TreeMap 区别</h3><p><code>TreeMap</code> 和 <code>HashMap</code> 都继承自 <code>AbstractMap</code> ，但是需要注意的是 <code>TreeMap</code> 它还实现了 <code>NavigableMap</code> 接口和 <code>SortedMap</code> 接口。</p>
<p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-15_f0b7565dcaf0e97aa02727b814b14539_6ycbzspzA5.png">TreeMap 继承关系图</p>
<p>实现 <code>NavigableMap</code> 接口让 <code>TreeMap</code> 有了对集合内元素的搜索的能力。</p>
<p>实现 <code>SortedMap</code> 接口让 <code>TreeMap</code> 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * @author shuang.kou</span><br><span class="line"> * @createTime 2020年06月15日 17:02:00</span><br><span class="line"> */</span><br><span class="line">public class Person &#123;</span><br><span class="line">    private Integer age;</span><br><span class="line"></span><br><span class="line">    public Person(Integer age) &#123;</span><br><span class="line">        this.age = age;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    public Integer getAge() &#123;</span><br><span class="line">        return age;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">        TreeMap&lt;Person, String&gt; treeMap = new TreeMap&lt;&gt;(new Comparator&lt;Person&gt;() &#123;</span><br><span class="line">            @Override</span><br><span class="line">            public int compare(Person person1, Person person2) &#123;</span><br><span class="line">                int num = person1.getAge() - person2.getAge();</span><br><span class="line">                return Integer.compare(num, 0);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;);</span><br><span class="line">        treeMap.put(new Person(3), &quot;person1&quot;);</span><br><span class="line">        treeMap.put(new Person(18), &quot;person2&quot;);</span><br><span class="line">        treeMap.put(new Person(35), &quot;person3&quot;);</span><br><span class="line">        treeMap.put(new Person(16), &quot;person4&quot;);</span><br><span class="line">        treeMap.entrySet().stream().forEach(personStringEntry -&gt; &#123;</span><br><span class="line">            System.out.println(personStringEntry.getValue());</span><br><span class="line">        &#125;);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>输出:</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">person1</span><br><span class="line">person4</span><br><span class="line">person2</span><br><span class="line">person3</span><br></pre></td></tr></table></figure>

<p>可以看出，<code>TreeMap</code> 中的元素已经是按照 <code>Person</code> 的 age 字段的升序来排列了。</p>
<p>上面，我们是通过传入匿名内部类的方式实现的，你可以将代码替换成 Lambda 表达式实现的方式：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">TreeMap&lt;Person, String&gt; treeMap = new TreeMap&lt;&gt;((person1, person2) -&gt; &#123;</span><br><span class="line">  int num = person1.getAge() - person2.getAge();</span><br><span class="line">  return Integer.compare(num, 0);</span><br><span class="line">&#125;);</span><br></pre></td></tr></table></figure>

<p><strong>综上，相比于 <code>HashMap</code> 来说 <code>TreeMap</code> 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。</strong></p>
<h3 id="HashSet-如何检查重复"><a href="#HashSet-如何检查重复" class="headerlink" title="# HashSet 如何检查重复?"></a><a href="#hashset-%E5%A6%82%E4%BD%95%E6%A3%80%E6%9F%A5%E9%87%8D%E5%A4%8D">#</a> HashSet 如何检查重复?</h3><p>以下内容摘自我的 Java 启蒙书《Head first java》第二版：</p>
<blockquote>
<p>当你把对象加入 <code>HashSet</code> 时，<code>HashSet</code> 会先计算对象的 <code>hashcode</code> 值来判断对象加入的位置，同时也会与其他加入的对象的 <code>hashcode</code> 值作比较，如果没有相符的 <code>hashcode</code>，<code>HashSet</code> 会假设对象没有重复出现。但是如果发现有相同 <code>hashcode</code> 值的对象，这时会调用 <code>equals()</code> 方法来检查 <code>hashcode</code> 相等的对象是否真的相同。如果两者相同，<code>HashSet</code> 就不会让加入操作成功。</p>
</blockquote>
<p>在 JDK 1.8 中，<code>HashSet</code> 的 <code>add()</code> 方法只是简单的调用了 <code>HashMap</code> 的 <code>put()</code> 方法，并且判断了一下返回值以确保是否有重复元素。直接看一下 <code>HashSet</code> 中的源码：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">// Returns: true if this set did not already contain the specified element</span><br><span class="line">// 返回值：当 set 中没有包含 add 的元素时返回真</span><br><span class="line">public boolean add(E e) &#123;</span><br><span class="line">        return map.put(e, PRESENT)==null;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>而在 <code>HashMap</code> 的 <code>putVal()</code> 方法中也能看到如下说明：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">// Returns : previous value, or null if none</span><br><span class="line">// 返回值：如果插入位置没有元素返回null，否则返回上一个元素</span><br><span class="line">final V putVal(int hash, K key, V value, boolean onlyIfAbsent,</span><br><span class="line">                   boolean evict) &#123;</span><br><span class="line">...</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>也就是说，在 JDK 1.8 中，实际上无论 <code>HashSet</code> 中是否已经存在了某元素，<code>HashSet</code> 都会直接插入，只是会在 <code>add()</code> 方法的返回值处告诉我们插入前是否存在相同元素。</p>
<h3 id="HashMap-的底层实现"><a href="#HashMap-的底层实现" class="headerlink" title="# HashMap 的底层实现"></a><a href="#hashmap-%E7%9A%84%E5%BA%95%E5%B1%82%E5%AE%9E%E7%8E%B0">#</a> HashMap 的底层实现</h3><h4 id="JDK-1-8-之前"><a href="#JDK-1-8-之前" class="headerlink" title="# JDK 1.8 之前"></a><a href="#jdk1-8-%E4%B9%8B%E5%89%8D">#</a> JDK 1.8 之前</h4><p>JDK 1.8 之前 <code>HashMap</code> 底层是 <strong>数组和链表</strong> 结合在一起使用也就是 <strong>链表散列</strong>。HashMap 通过 key 的 <code>hashcode</code> 经过扰动函数处理过后得到 hash 值，然后通过 <code>(n - 1) &amp; hash</code> 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。</p>
<p>所谓扰动函数指的就是 HashMap 的 <code>hash</code> 方法。使用 <code>hash</code> 方法也就是扰动函数是为了防止一些实现比较差的 <code>hashCode()</code> 方法 换句话说使用扰动函数之后可以减少碰撞。</p>
<p><strong>JDK 1.8 HashMap 的 hash 方法源码:</strong></p>
<p>JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">static final int hash(Object key) &#123;</span><br><span class="line">      int h;</span><br><span class="line">      // key.hashCode()：返回散列值也就是hashcode</span><br><span class="line">      // ^：按位异或</span><br><span class="line">      // &gt;&gt;&gt;:无符号右移，忽略符号位，空位都以0补齐</span><br><span class="line">      return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);</span><br><span class="line">  &#125;</span><br></pre></td></tr></table></figure>

<p>对比一下 JDK 1.7 的 HashMap 的 hash 方法源码.</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">static int hash(int h) &#123;</span><br><span class="line">    // This function ensures that hashCodes that differ only by</span><br><span class="line">    // constant multiples at each bit position have a bounded</span><br><span class="line">    // number of collisions (approximately 8 at default load factor).</span><br><span class="line"></span><br><span class="line">    h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);</span><br><span class="line">    return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>相比于 JDK 1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。</p>
<p>所谓 <strong>“拉链法”</strong> 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。</p>
<p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-22_c9b537e3c821176be80de8a4ab598116_u8Vl9Epakn.png">jdk 1.8 之前的内部结构 - HashMap</p>
<h4 id="JDK-1-8-之后"><a href="#JDK-1-8-之后" class="headerlink" title="# JDK 1.8 之后"></a><a href="#jdk1-8-%E4%B9%8B%E5%90%8E">#</a> JDK 1.8 之后</h4><p>相比于之前的版本， JDK 1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。</p>
<p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-27_c4144616416adc9f2e86ffba2c6f99d3_DP8P17VN2X.png">jdk 1.8 之后的内部结构 - HashMap</p>
<blockquote>
<p>TreeMap、TreeSet 以及 JDK 1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。</p>
</blockquote>
<p>我们来结合源码分析一下 <code>HashMap</code> 链表到红黑树的转换。</p>
<p><strong>1、 <code>putVal</code> 方法中执行链表转红黑树的判断逻辑。</strong></p>
<p>链表的长度大于 8 的时候，就执行 <code>treeifyBin</code> （转换红黑树）的逻辑。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">// 遍历链表</span><br><span class="line">for (int binCount = 0; ; ++binCount) &#123;</span><br><span class="line">    // 遍历到链表最后一个节点</span><br><span class="line">    if ((e = p.next) == null) &#123;</span><br><span class="line">        p.next = newNode(hash, key, value, null);</span><br><span class="line">        // 如果链表元素个数大于等于TREEIFY_THRESHOLD（8）</span><br><span class="line">        if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st</span><br><span class="line">            // 红黑树转换（并不会直接转换成红黑树）</span><br><span class="line">            treeifyBin(tab, hash);</span><br><span class="line">        break;</span><br><span class="line">    &#125;</span><br><span class="line">    if (e.hash == hash &amp;&amp;</span><br><span class="line">        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">        break;</span><br><span class="line">    p = e;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>2、<code>treeifyBin</code> 方法中判断是否真的转换为红黑树。</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line">final void treeifyBin(Node&lt;K,V&gt;[] tab, int hash) &#123;</span><br><span class="line">    int n, index; Node&lt;K,V&gt; e;</span><br><span class="line">    // 判断当前数组的长度是否小于 64</span><br><span class="line">    if (tab == null || (n = tab.length) &lt; MIN_TREEIFY_CAPACITY)</span><br><span class="line">        // 如果当前数组的长度小于 64，那么会选择先进行数组扩容</span><br><span class="line">        resize();</span><br><span class="line">    else if ((e = tab[index = (n - 1) &amp; hash]) != null) &#123;</span><br><span class="line">        // 否则才将列表转换为红黑树</span><br><span class="line"></span><br><span class="line">        TreeNode&lt;K,V&gt; hd = null, tl = null;</span><br><span class="line">        do &#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; p = replacementTreeNode(e, null);</span><br><span class="line">            if (tl == null)</span><br><span class="line">                hd = p;</span><br><span class="line">            else &#123;</span><br><span class="line">                p.prev = tl;</span><br><span class="line">                tl.next = p;</span><br><span class="line">            &#125;</span><br><span class="line">            tl = p;</span><br><span class="line">        &#125; while ((e = e.next) != null);</span><br><span class="line">        if ((tab[index] = hd) != null)</span><br><span class="line">            hd.treeify(tab);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。</p>
<h3 id="HashMap-的长度为什么是-2-的幂次方"><a href="#HashMap-的长度为什么是-2-的幂次方" class="headerlink" title="# HashMap 的长度为什么是 2 的幂次方"></a><a href="#hashmap-%E7%9A%84%E9%95%BF%E5%BA%A6%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF-2-%E7%9A%84%E5%B9%82%E6%AC%A1%E6%96%B9">#</a> HashMap 的长度为什么是 2 的幂次方</h3><p>为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值 - 2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是 “ <code>(n - 1) &amp; hash</code>”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。</p>
<p><strong>这个算法应该如何设计呢？</strong></p>
<p>我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：<strong>“取余 (%) 操作中如果除数是 2 的幂次则等价于与其除数减一的与 (&amp;) 操作（也就是说 hash%length&#x3D;&#x3D;hash&amp;(length-1)的前提是 length 是 2 的 n 次方；）。”</strong> 并且 <strong>采用二进制位操作 &amp;，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。</strong></p>
<h3 id="HashMap-多线程操作导致死循环问题"><a href="#HashMap-多线程操作导致死循环问题" class="headerlink" title="# HashMap 多线程操作导致死循环问题"></a><a href="#hashmap-%E5%A4%9A%E7%BA%BF%E7%A8%8B%E6%93%8D%E4%BD%9C%E5%AF%BC%E8%87%B4%E6%AD%BB%E5%BE%AA%E7%8E%AF%E9%97%AE%E9%A2%98">#</a> HashMap 多线程操作导致死循环问题</h3><p>JDK 1.7 及之前版本的 <code>HashMap</code> 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。</p>
<p>为了解决这个问题，JDK 1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 <code>HashMap</code>，因为多线程下使用 <code>HashMap</code> 还是会存在数据覆盖的问题。并发环境下，推荐使用 <code>ConcurrentHashMap</code> 。</p>
<p>一般面试中这样介绍就差不多，不需要记各种细节，个人觉得也没必要记。如果想要详细了解 <code>HashMap</code> 扩容导致死循环问题，可以看看耗子叔的这篇文章：<a target="_blank" rel="noopener" href="https://coolshell.cn/articles/9606.html">Java HashMap 的死循环 open in new window</a>。</p>
<h3 id="HashMap-为什么线程不安全？"><a href="#HashMap-为什么线程不安全？" class="headerlink" title="# HashMap 为什么线程不安全？"></a><a href="#hashmap-%E4%B8%BA%E4%BB%80%E4%B9%88%E7%BA%BF%E7%A8%8B%E4%B8%8D%E5%AE%89%E5%85%A8">#</a> HashMap 为什么线程不安全？</h3><p>JDK 1.7 及之前版本，在多线程环境下，<code>HashMap</code> 扩容时会造成死循环和数据丢失的问题。</p>
<p>数据丢失这个在 JDK 1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。</p>
<p>JDK 1.8 后，在 <code>HashMap</code> 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 <code>HashMap</code> 的 <code>put</code> 操作会导致线程不安全，具体来说会有数据覆盖的风险。</p>
<p>举个例子：</p>
<ul>
<li>两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。</li>
<li>不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。</li>
<li>随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。</li>
</ul>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">public V put(K key, V value) &#123;</span><br><span class="line">    return putVal(hash(key), key, value, false, true);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">final V putVal(int hash, K key, V value, boolean onlyIfAbsent,</span><br><span class="line">                   boolean evict) &#123;</span><br><span class="line">    // ...</span><br><span class="line">    // 判断是否出现 hash 碰撞</span><br><span class="line">    // (n - 1) &amp; hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)</span><br><span class="line">    if ((p = tab[i = (n - 1) &amp; hash]) == null)</span><br><span class="line">        tab[i] = newNode(hash, key, value, null);</span><br><span class="line">    // 桶中已经存在元素（处理hash冲突）</span><br><span class="line">    else &#123;</span><br><span class="line">    // ...</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>还有一种情况是这两个线程同时 <code>put</code> 操作导致 <code>size</code> 的值不正确，进而导致数据覆盖的问题：</p>
<ol>
<li>线程 1 执行 <code>if(++size &gt; threshold)</code> 判断时，假设获得 <code>size</code> 的值为 10，由于时间片耗尽挂起。</li>
<li>线程 2 也执行 <code>if(++size &gt; threshold)</code> 判断，获得 <code>size</code> 的值也为 10，并将元素插入到该桶位中，并将 <code>size</code> 的值更新为 11。</li>
<li>随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。</li>
<li>线程 1、2 都执行了一次 <code>put</code> 操作，但是 <code>size</code> 的值只增加了 1，也就导致实际上只有一个元素被添加到了 <code>HashMap</code> 中。</li>
</ol>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">public V put(K key, V value) &#123;</span><br><span class="line">    return putVal(hash(key), key, value, false, true);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">final V putVal(int hash, K key, V value, boolean onlyIfAbsent,</span><br><span class="line">                   boolean evict) &#123;</span><br><span class="line">    // ...</span><br><span class="line">    // 实际大小大于阈值则扩容</span><br><span class="line">    if (++size &gt; threshold)</span><br><span class="line">        resize();</span><br><span class="line">    // 插入后回调</span><br><span class="line">    afterNodeInsertion(evict);</span><br><span class="line">    return null;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="HashMap-常见的遍历方式"><a href="#HashMap-常见的遍历方式" class="headerlink" title="# HashMap 常见的遍历方式?"></a><a href="#hashmap-%E5%B8%B8%E8%A7%81%E7%9A%84%E9%81%8D%E5%8E%86%E6%96%B9%E5%BC%8F">#</a> HashMap 常见的遍历方式?</h3><p><a target="_blank" rel="noopener" href="https://mp.weixin.qq.com/s/zQBN3UvJDhRTKP6SzcZFKw">HashMap 的 7 种遍历方式与性能分析！open in new window</a></p>
<p><strong>🐛 修正（参见：<a target="_blank" rel="noopener" href="https://github.com/Snailclimb/JavaGuide/issues/1411">issue#1411open in new window</a>）</strong>：</p>
<p>这篇文章对于 parallelStream 遍历方式的性能分析有误，先说结论：<strong>存在阻塞时 parallelStream 性能最高, 非阻塞时 parallelStream 性能最低</strong> 。</p>
<p>当遍历不存在阻塞时, parallelStream 的性能是最低的：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Benchmark               Mode  Cnt     Score      Error  Units</span><br><span class="line">Test.entrySet           avgt    5   288.651 ±   10.536  ns/op</span><br><span class="line">Test.keySet             avgt    5   584.594 ±   21.431  ns/op</span><br><span class="line">Test.lambda             avgt    5   221.791 ±   10.198  ns/op</span><br><span class="line">Test.parallelStream     avgt    5  6919.163 ± 1116.139  ns/op</span><br></pre></td></tr></table></figure>

<p>加入阻塞代码 <code>Thread.sleep(10)</code> 后, parallelStream 的性能才是最高的:</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Benchmark               Mode  Cnt           Score          Error  Units</span><br><span class="line">Test.entrySet           avgt    5  1554828440.000 ± 23657748.653  ns/op</span><br><span class="line">Test.keySet             avgt    5  1550612500.000 ±  6474562.858  ns/op</span><br><span class="line">Test.lambda             avgt    5  1551065180.000 ± 19164407.426  ns/op</span><br><span class="line">Test.parallelStream     avgt    5   186345456.667 ±  3210435.590  ns/op</span><br></pre></td></tr></table></figure>

<h3 id="ConcurrentHashMap-和-Hashtable-的区别"><a href="#ConcurrentHashMap-和-Hashtable-的区别" class="headerlink" title="# ConcurrentHashMap 和 Hashtable 的区别"></a><a href="#concurrenthashmap-%E5%92%8C-hashtable-%E7%9A%84%E5%8C%BA%E5%88%AB">#</a> ConcurrentHashMap 和 Hashtable 的区别</h3><p><code>ConcurrentHashMap</code> 和 <code>Hashtable</code> 的区别主要体现在实现线程安全的方式上不同。</p>
<ul>
<li><strong>底层数据结构：</strong> JDK 1.7 的 <code>ConcurrentHashMap</code> 底层采用 <strong>分段的数组 + 链表</strong> 实现，JDK 1.8 采用的数据结构跟 <code>HashMap1.8</code> 的结构一样，数组 + 链表 &#x2F; 红黑二叉树。<code>Hashtable</code> 和 JDK 1.8 之前的 <code>HashMap</code> 的底层数据结构类似都是采用 <strong>数组 + 链表</strong> 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；</li>
<li><strong>实现线程安全的方式（重要）：</strong><ul>
<li>在 JDK 1.7 的时候，<code>ConcurrentHashMap</code> 对整个桶数组进行了分割分段 (<code>Segment</code>，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。</li>
<li>到了 JDK 1.8 的时候，<code>ConcurrentHashMap</code> 已经摒弃了 <code>Segment</code> 的概念，而是直接用 <code>Node</code> 数组 + 链表 + 红黑树的数据结构来实现，并发控制使用 <code>synchronized</code> 和 CAS 来操作。（JDK 1.6 以后 <code>synchronized</code> 锁做了很多优化） 整个看起来就像是优化过且线程安全的 <code>HashMap</code>，虽然在 JDK 1.8 中还能看到 <code>Segment</code> 的数据结构，但是已经简化了属性，只是为了兼容旧版本；</li>
<li><strong><code>Hashtable</code> (同一把锁)</strong> : 使用 <code>synchronized</code> 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。</li>
</ul>
</li>
</ul>
<p>下面，我们再来看看两者底层数据结构的对比图。</p>
<p><strong>Hashtable</strong> :</p>
<p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-22_c9b537e3c821176be80de8a4ab598116_u8Vl9Epakn.png">Hashtable 的内部结构</p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/chengxiao/p/6842045.html%3E">https://www.cnblogs.com/chengxiao/p/6842045.html&gt;</a></p>
<p><strong>JDK 1.7 的 ConcurrentHashMap</strong>：</p>
<p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-34_aaa7445ec1bdbd5861d2c554402f139d_tr5LFkmpWr.png">Java 7 ConcurrentHashMap 存储结构</p>
<p><code>ConcurrentHashMap</code> 是由 <code>Segment</code> 数组结构和 <code>HashEntry</code> 数组结构组成。</p>
<p><code>Segment</code> 数组中的每个元素包含一个 <code>HashEntry</code> 数组，每个 <code>HashEntry</code> 数组属于链表结构。</p>
<p><strong>JDK 1.8 的 ConcurrentHashMap</strong>：</p>
<p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-42_9d2250da5eb4b2155d8ec0ef7dcce78f_QMXDYI93SA.png">Java 8 ConcurrentHashMap 存储结构</p>
<p>JDK 1.8 的 <code>ConcurrentHashMap</code> 不再是 <strong>Segment 数组 + HashEntry 数组 + 链表</strong>，而是 <strong>Node 数组 + 链表 &#x2F; 红黑树</strong>。不过，Node 只能用于链表的情况，红黑树的情况需要使用 **<code>TreeNode</code>**。当冲突链表达到一定长度时，链表会转换成红黑树。</p>
<p><code>TreeNode</code> 是存储红黑树节点，被 <code>TreeBin</code> 包装。<code>TreeBin</code> 通过 <code>root</code> 属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 <code>ConcurrentHashMap</code> 中 <code>TreeBin</code> 通过 <code>waiter</code> 属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">static final class TreeBin&lt;K,V&gt; extends Node&lt;K,V&gt; &#123;</span><br><span class="line">        TreeNode&lt;K,V&gt; root;</span><br><span class="line">        volatile TreeNode&lt;K,V&gt; first;</span><br><span class="line">        volatile Thread waiter;</span><br><span class="line">        volatile int lockState;</span><br><span class="line">        // values for lockState</span><br><span class="line">        static final int WRITER = 1; // set while holding write lock</span><br><span class="line">        static final int WAITER = 2; // set when waiting for write lock</span><br><span class="line">        static final int READER = 4; // increment value for setting read lock</span><br><span class="line">...</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="ConcurrentHashMap-线程安全的具体实现方式-底层具体实现"><a href="#ConcurrentHashMap-线程安全的具体实现方式-底层具体实现" class="headerlink" title="# ConcurrentHashMap 线程安全的具体实现方式 &#x2F; 底层具体实现"></a><a href="#concurrenthashmap-%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E5%85%B7%E4%BD%93%E5%AE%9E%E7%8E%B0%E6%96%B9%E5%BC%8F-%E5%BA%95%E5%B1%82%E5%85%B7%E4%BD%93%E5%AE%9E%E7%8E%B0">#</a> ConcurrentHashMap 线程安全的具体实现方式 &#x2F; 底层具体实现</h3><h4 id="JDK-1-8-之前-1"><a href="#JDK-1-8-之前-1" class="headerlink" title="# JDK 1.8 之前"></a><a href="#jdk1-8-%E4%B9%8B%E5%89%8D-1">#</a> JDK 1.8 之前</h4><p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-34_aaa7445ec1bdbd5861d2c554402f139d_tr5LFkmpWr.png">Java 7 ConcurrentHashMap 存储结构</p>
<p>首先将数据分为一段一段（这个 “段” 就是 <code>Segment</code>）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。</p>
<p><strong><code>ConcurrentHashMap</code> 是由 <code>Segment</code> 数组结构和 <code>HashEntry</code> 数组结构组成</strong>。</p>
<p><code>Segment</code> 继承了 <code>ReentrantLock</code>, 所以 <code>Segment</code> 是一种可重入锁，扮演锁的角色。<code>HashEntry</code> 用于存储键值对数据。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">static class Segment&lt;K,V&gt; extends ReentrantLock implements Serializable &#123;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>一个 <code>ConcurrentHashMap</code> 里包含一个 <code>Segment</code> 数组，<code>Segment</code> 的个数一旦<strong>初始化就不能改变</strong>。 <code>Segment</code> 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。</p>
<p><code>Segment</code> 的结构和 <code>HashMap</code> 类似，是一种数组和链表结构，一个 <code>Segment</code> 包含一个 <code>HashEntry</code> 数组，每个 <code>HashEntry</code> 是一个链表结构的元素，每个 <code>Segment</code> 守护着一个 <code>HashEntry</code> 数组里的元素，当对 <code>HashEntry</code> 数组的数据进行修改时，必须首先获得对应的 <code>Segment</code> 的锁。也就是说，对同一 <code>Segment</code> 的并发写入会被阻塞，不同 <code>Segment</code> 的写入是可以并发执行的。</p>
<h4 id="JDK-1-8-之后-1"><a href="#JDK-1-8-之后-1" class="headerlink" title="# JDK 1.8 之后"></a><a href="#jdk1-8-%E4%B9%8B%E5%90%8E-1">#</a> JDK 1.8 之后</h4><p><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/obsition/2024-02-03_12-45-42_9d2250da5eb4b2155d8ec0ef7dcce78f_QMXDYI93SA.png">Java 8 ConcurrentHashMap 存储结构</p>
<p>Java 8 几乎完全重写了 <code>ConcurrentHashMap</code>，代码量从原来 Java 7 中的 1000 多行，变成了现在的 6000 多行。</p>
<p><code>ConcurrentHashMap</code> 取消了 <code>Segment</code> 分段锁，采用 <code>Node + CAS + synchronized</code> 来保证并发安全。数据结构跟 <code>HashMap</code> 1.8 的结构类似，数组 + 链表 &#x2F; 红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O (N)）转换为红黑树（寻址时间复杂度为 O (log (N))）。</p>
<p>Java 8 中，锁粒度更细，<code>synchronized</code> 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。</p>
<h3 id="JDK-1-7-和-JDK-1-8-的-ConcurrentHashMap-实现有什么不同？"><a href="#JDK-1-7-和-JDK-1-8-的-ConcurrentHashMap-实现有什么不同？" class="headerlink" title="# JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？"></a><a href="#jdk-1-7-%E5%92%8C-jdk-1-8-%E7%9A%84-concurrenthashmap-%E5%AE%9E%E7%8E%B0%E6%9C%89%E4%BB%80%E4%B9%88%E4%B8%8D%E5%90%8C">#</a> JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？</h3><ul>
<li><strong>线程安全实现方式</strong>：JDK 1.7 采用 <code>Segment</code> 分段锁来保证安全， <code>Segment</code> 是继承自 <code>ReentrantLock</code>。JDK 1.8 放弃了 <code>Segment</code> 分段锁的设计，采用 <code>Node + CAS + synchronized</code> 保证线程安全，锁粒度更细，<code>synchronized</code> 只锁定当前链表或红黑二叉树的首节点。</li>
<li><strong>Hash 碰撞解决方法</strong> : JDK 1.7 采用拉链法，JDK 1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。</li>
<li><strong>并发度</strong>：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。</li>
</ul>
<h3 id="ConcurrentHashMap-为什么-key-和-value-不能为-null？"><a href="#ConcurrentHashMap-为什么-key-和-value-不能为-null？" class="headerlink" title="# ConcurrentHashMap 为什么 key 和 value 不能为 null？"></a><a href="#concurrenthashmap-%E4%B8%BA%E4%BB%80%E4%B9%88-key-%E5%92%8C-value-%E4%B8%8D%E8%83%BD%E4%B8%BA-null">#</a> ConcurrentHashMap 为什么 key 和 value 不能为 null？</h3><p><code>ConcurrentHashMap</code> 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 <code>ConcurrentHashMap</code> 中，还是根本没有这个键。同样，如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 <code>ConcurrentHashMap</code> 中的，还是因为找不到对应的键而返回的。</p>
<p>拿 get 方法取值来说，返回的结果为 null 存在两种情况：</p>
<ul>
<li>值没有在集合中 ；</li>
<li>值本身就是 null。</li>
</ul>
<p>这也就是二义性的由来。</p>
<p>具体可以参考 <a target="_blank" rel="noopener" href="https://javaguide.cn/java/collection/concurrent-hash-map-source-code.html">ConcurrentHashMap 源码分析 open in new window</a> 。</p>
<p>多线程环境下，存在一个线程操作该 <code>ConcurrentHashMap</code> 时，其他的线程将该 <code>ConcurrentHashMap</code> 修改的情况，所以无法通过 <code>containsKey(key)</code> 来判断否存在这个键值对，也就没办法解决二义性问题了。</p>
<p>与此形成对比的是，<code>HashMap</code> 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 <code>HashMap</code> 修改的情况，所以可以通过 <code>contains(key)</code> 来做判断是否存在这个键值对，从而做相应的处理，也就不存在二义性问题。</p>
<p>也就是说，多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。</p>
<p>如果你确实需要在 ConcurrentHashMap 中使用 null 的话，可以使用一个特殊的静态空对象来代替 null。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">public static final Object NULL = new Object();</span><br></pre></td></tr></table></figure>

<p>最后，再分享一下 <code>ConcurrentHashMap</code> 作者本人 (Doug Lea) 对于这个问题的回答：</p>
<blockquote>
<p>The main reason that nulls aren’t allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can’t be accommodated. The main one is that if <code>map.get(key)</code> returns <code>null</code>, you can’t detect whether the key explicitly maps to <code>null</code> vs the key isn’t mapped. In a non-concurrent map, you can check this via <code>map.contains(key)</code>, but in a concurrent one, the map might have changed between calls.</p>
</blockquote>
<p>翻译过来之后的，大致意思还是单线程下可以容忍歧义，而多线程下无法容忍。</p>
<h3 id="ConcurrentHashMap-能保证复合操作的原子性吗？"><a href="#ConcurrentHashMap-能保证复合操作的原子性吗？" class="headerlink" title="# ConcurrentHashMap 能保证复合操作的原子性吗？"></a><a href="#concurrenthashmap-%E8%83%BD%E4%BF%9D%E8%AF%81%E5%A4%8D%E5%90%88%E6%93%8D%E4%BD%9C%E7%9A%84%E5%8E%9F%E5%AD%90%E6%80%A7%E5%90%97">#</a> ConcurrentHashMap 能保证复合操作的原子性吗？</h3><p><code>ConcurrentHashMap</code> 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK 1.7 及之前版本的 <code>HashMap</code> 多线程操作导致死循环问题。但是，这并不意味着它可以保证所有的复合操作都是原子性的，一定不要搞混了！</p>
<p>复合操作是指由多个基本操作 (如 <code>put</code>、<code>get</code>、<code>remove</code>、<code>containsKey</code> 等) 组成的操作，例如先判断某个键是否存在 <code>containsKey(key)</code>，然后根据结果进行插入或更新 <code>put(key, value)</code>。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。</p>
<p>例如，有两个线程 A 和 B 同时对 <code>ConcurrentHashMap</code> 进行复合操作，如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">// 线程 A</span><br><span class="line">if (!map.containsKey(key)) &#123;</span><br><span class="line">map.put(key, value);</span><br><span class="line">&#125;</span><br><span class="line">// 线程 B</span><br><span class="line">if (!map.containsKey(key)) &#123;</span><br><span class="line">map.put(key, anotherValue);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如果线程 A 和 B 的执行顺序是这样：</p>
<ol>
<li>线程 A 判断 map 中不存在 key</li>
<li>线程 B 判断 map 中不存在 key</li>
<li>线程 B 将 (key, anotherValue) 插入 map</li>
<li>线程 A 将 (key, value) 插入 map</li>
</ol>
<p>那么最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题。</p>
<p><strong>那如何保证 <code>ConcurrentHashMap</code> 复合操作的原子性呢？</strong></p>
<p><code>ConcurrentHashMap</code> 提供了一些原子性的复合操作，如 <code>putIfAbsent</code>、<code>compute</code>、<code>computeIfAbsent</code> 、<code>computeIfPresent</code>、<code>merge</code> 等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。</p>
<p>上面的代码可以改写为：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">// 线程 A</span><br><span class="line">map.putIfAbsent(key, value);</span><br><span class="line">// 线程 B</span><br><span class="line">map.putIfAbsent(key, anotherValue);</span><br></pre></td></tr></table></figure>

<p>或者：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">// 线程 A</span><br><span class="line">map.computeIfAbsent(key, k -&gt; value);</span><br><span class="line">// 线程 B</span><br><span class="line">map.computeIfAbsent(key, k -&gt; anotherValue);</span><br></pre></td></tr></table></figure>

<p>很多同学可能会说了，这种情况也能加锁同步呀！确实可以，但不建议使用加锁的同步机制，违背了使用 <code>ConcurrentHashMap</code> 的初衷。在使用 <code>ConcurrentHashMap</code> 的时候，尽量使用这些原子性的复合操作方法来保证原子性。</p>
<h2 id="Collections-工具类（不重要）"><a href="#Collections-工具类（不重要）" class="headerlink" title="# Collections 工具类（不重要）"></a><a href="#collections-%E5%B7%A5%E5%85%B7%E7%B1%BB-%E4%B8%8D%E9%87%8D%E8%A6%81">#</a> Collections 工具类（不重要）</h2><p><strong><code>Collections</code> 工具类常用方法</strong>:</p>
<ul>
<li>排序</li>
<li>查找, 替换操作</li>
<li>同步控制 (不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)</li>
</ul>
<h3 id="排序操作"><a href="#排序操作" class="headerlink" title="# 排序操作"></a><a href="#%E6%8E%92%E5%BA%8F%E6%93%8D%E4%BD%9C">#</a> 排序操作</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">void reverse(List list)//反转</span><br><span class="line">void shuffle(List list)//随机排序</span><br><span class="line">void sort(List list)//按自然排序的升序排序</span><br><span class="line">void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑</span><br><span class="line">void swap(List list, int i , int j)//交换两个索引位置的元素</span><br><span class="line">void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面</span><br></pre></td></tr></table></figure>

<h3 id="查找-替换操作"><a href="#查找-替换操作" class="headerlink" title="# 查找, 替换操作"></a><a href="#%E6%9F%A5%E6%89%BE-%E6%9B%BF%E6%8D%A2%E6%93%8D%E4%BD%9C">#</a> 查找, 替换操作</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的</span><br><span class="line">int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)</span><br><span class="line">int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)</span><br><span class="line">void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素</span><br><span class="line">int frequency(Collection c, Object o)//统计元素出现次数</span><br><span class="line">int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)</span><br><span class="line">boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素</span><br></pre></td></tr></table></figure>

<h3 id="同步控制"><a href="#同步控制" class="headerlink" title="# 同步控制"></a><a href="#%E5%90%8C%E6%AD%A5%E6%8E%A7%E5%88%B6">#</a> 同步控制</h3><p><code>Collections</code> 提供了多个 <code>synchronizedXxx()</code> 方法 ·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。</p>
<p>我们知道 <code>HashSet</code>，<code>TreeSet</code>，<code>ArrayList</code>, <code>LinkedList</code>, <code>HashMap</code>, <code>TreeMap</code> 都是线程不安全的。<code>Collections</code> 提供了多个静态方法可以把他们包装成线程同步的集合。</p>
<p><strong>最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。</strong></p>
<p>方法如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">synchronizedCollection(Collection&lt;T&gt;  c) //返回指定 collection 支持的同步（线程安全的）collection。</span><br><span class="line">synchronizedList(List&lt;T&gt; list)//返回指定列表支持的同步（线程安全的）List。</span><br><span class="line">synchronizedMap(Map&lt;K,V&gt; m) //返回由指定映射支持的同步（线程安全的）Map。</span><br><span class="line">synchronizedSet(Set&lt;T&gt; s) //返回指定 set 支持的同步（线程安全的）set。</span><br></pre></td></tr></table></figure>

</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta"><i class="fas fa-circle-user fa-fw"></i>文章作者: </span><span class="post-copyright-info"><a href="https://ko25891wan.gitlab.io">十一星野</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta"><i class="fas fa-square-arrow-up-right fa-fw"></i>文章链接: </span><span class="post-copyright-info"><a href="https://ko25891wan.gitlab.io/2024/01/fd03bd589630.html">https://ko25891wan.gitlab.io/2024/01/fd03bd589630.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta"><i class="fas fa-circle-exclamation fa-fw"></i>版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://ko25891wan.gitlab.io" target="_blank">小小程序员</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"></div><div class="post_share"></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2024/01/01e1236339d4.html" title="MyBatis常见面试题总结"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">MyBatis常见面试题总结</div></div></a></div><div class="next-post pull-right"><a href="/2024/01/0147eb45eb00.html" title="Java集合常见面试题总结(上)"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Java集合常见面试题总结(上)</div></div></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://qiniu.ko25891wan.top/%E6%97%A5%E8%AE%B0%E8%BD%AF%E4%BB%B6/%E5%A4%B4%E5%83%8F/%E7%81%B0%E5%A4%AA%E7%8B%BC.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">十一星野</div><div class="author-info__description">归途也还可爱</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">120</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">4</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">22</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://gitlab.com/ko25891wan/ko25891wan.gitlab.io"><i class="fab fa-github"></i><span>关注我</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://gitlab.com/ko25891wan/ko25891wan.gitlab.io" target="_blank" title="Github"><i class="fab fa-github" style="color: #24292e;"></i></a><a class="social-icon" href="https://gitlab.com/ko25891wan/ko25891wan.gitlab.io" target="_blank" title="Gitlab"><i class="fab fa-gitlab" style="color: #24292e;"></i></a><a class="social-icon" href="mailto:ko25891wan@outlook.com" target="_blank" title="Email"><i class="fas fa-envelope" style="color: #4a7dbe;"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">This is my Blog</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#Map%EF%BC%88%E9%87%8D%E8%A6%81%EF%BC%89"><span class="toc-number">1.</span> <span class="toc-text"> Map（重要）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E5%92%8C-Hashtable-%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-number">1.1.</span> <span class="toc-text"> HashMap 和 Hashtable 的区别</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E5%92%8C-HashSet-%E5%8C%BA%E5%88%AB"><span class="toc-number">1.2.</span> <span class="toc-text"> HashMap 和 HashSet 区别</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E5%92%8C-TreeMap-%E5%8C%BA%E5%88%AB"><span class="toc-number">1.3.</span> <span class="toc-text"> HashMap 和 TreeMap 区别</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashSet-%E5%A6%82%E4%BD%95%E6%A3%80%E6%9F%A5%E9%87%8D%E5%A4%8D"><span class="toc-number">1.4.</span> <span class="toc-text"> HashSet 如何检查重复?</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E7%9A%84%E5%BA%95%E5%B1%82%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.5.</span> <span class="toc-text"> HashMap 的底层实现</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#JDK-1-8-%E4%B9%8B%E5%89%8D"><span class="toc-number">1.5.1.</span> <span class="toc-text"> JDK 1.8 之前</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#JDK-1-8-%E4%B9%8B%E5%90%8E"><span class="toc-number">1.5.2.</span> <span class="toc-text"> JDK 1.8 之后</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E7%9A%84%E9%95%BF%E5%BA%A6%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF-2-%E7%9A%84%E5%B9%82%E6%AC%A1%E6%96%B9"><span class="toc-number">1.6.</span> <span class="toc-text"> HashMap 的长度为什么是 2 的幂次方</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E5%A4%9A%E7%BA%BF%E7%A8%8B%E6%93%8D%E4%BD%9C%E5%AF%BC%E8%87%B4%E6%AD%BB%E5%BE%AA%E7%8E%AF%E9%97%AE%E9%A2%98"><span class="toc-number">1.7.</span> <span class="toc-text"> HashMap 多线程操作导致死循环问题</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E4%B8%BA%E4%BB%80%E4%B9%88%E7%BA%BF%E7%A8%8B%E4%B8%8D%E5%AE%89%E5%85%A8%EF%BC%9F"><span class="toc-number">1.8.</span> <span class="toc-text"> HashMap 为什么线程不安全？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap-%E5%B8%B8%E8%A7%81%E7%9A%84%E9%81%8D%E5%8E%86%E6%96%B9%E5%BC%8F"><span class="toc-number">1.9.</span> <span class="toc-text"> HashMap 常见的遍历方式?</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ConcurrentHashMap-%E5%92%8C-Hashtable-%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-number">1.10.</span> <span class="toc-text"> ConcurrentHashMap 和 Hashtable 的区别</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ConcurrentHashMap-%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E5%85%B7%E4%BD%93%E5%AE%9E%E7%8E%B0%E6%96%B9%E5%BC%8F-%E5%BA%95%E5%B1%82%E5%85%B7%E4%BD%93%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.11.</span> <span class="toc-text"> ConcurrentHashMap 线程安全的具体实现方式 &#x2F; 底层具体实现</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#JDK-1-8-%E4%B9%8B%E5%89%8D-1"><span class="toc-number">1.11.1.</span> <span class="toc-text"> JDK 1.8 之前</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#JDK-1-8-%E4%B9%8B%E5%90%8E-1"><span class="toc-number">1.11.2.</span> <span class="toc-text"> JDK 1.8 之后</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#JDK-1-7-%E5%92%8C-JDK-1-8-%E7%9A%84-ConcurrentHashMap-%E5%AE%9E%E7%8E%B0%E6%9C%89%E4%BB%80%E4%B9%88%E4%B8%8D%E5%90%8C%EF%BC%9F"><span class="toc-number">1.12.</span> <span class="toc-text"> JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ConcurrentHashMap-%E4%B8%BA%E4%BB%80%E4%B9%88-key-%E5%92%8C-value-%E4%B8%8D%E8%83%BD%E4%B8%BA-null%EF%BC%9F"><span class="toc-number">1.13.</span> <span class="toc-text"> ConcurrentHashMap 为什么 key 和 value 不能为 null？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ConcurrentHashMap-%E8%83%BD%E4%BF%9D%E8%AF%81%E5%A4%8D%E5%90%88%E6%93%8D%E4%BD%9C%E7%9A%84%E5%8E%9F%E5%AD%90%E6%80%A7%E5%90%97%EF%BC%9F"><span class="toc-number">1.14.</span> <span class="toc-text"> ConcurrentHashMap 能保证复合操作的原子性吗？</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Collections-%E5%B7%A5%E5%85%B7%E7%B1%BB%EF%BC%88%E4%B8%8D%E9%87%8D%E8%A6%81%EF%BC%89"><span class="toc-number">2.</span> <span class="toc-text"> Collections 工具类（不重要）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F%E6%93%8D%E4%BD%9C"><span class="toc-number">2.1.</span> <span class="toc-text"> 排序操作</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9F%A5%E6%89%BE-%E6%9B%BF%E6%8D%A2%E6%93%8D%E4%BD%9C"><span class="toc-number">2.2.</span> <span class="toc-text"> 查找, 替换操作</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%90%8C%E6%AD%A5%E6%8E%A7%E5%88%B6"><span class="toc-number">2.3.</span> <span class="toc-text"> 同步控制</span></a></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2024/02/c60470b9a892.html" title="Java集合使用注意事项总结">Java集合使用注意事项总结</a><time datetime="2024-02-03T04:58:22.000Z" title="发表于 2024-02-03 12:58:22">2024-02-03</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2024/02/81fb7a201f29.html" title="无题">无题</a><time datetime="2024-02-03T03:15:31.812Z" title="发表于 2024-02-03 11:15:31">2024-02-03</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2024/01/5737c1ec69a9.html" title="Wed Jan 17 2024 00:00:00 GMT+0800 (中国标准时间)">Wed Jan 17 2024 00:00:00 GMT+0800 (中国标准时间)</a><time datetime="2024-01-31T06:56:16.000Z" title="发表于 2024-01-31 14:56:16">2024-01-31</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2024/01/f510db7d2f19.html" title="Spring常见面试题总结">Spring常见面试题总结</a><time datetime="2024-01-31T06:55:58.000Z" title="发表于 2024-01-31 14:55:58">2024-01-31</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2024/01/9be065e9f288.html" title="redis 面试">redis 面试</a><time datetime="2024-01-31T06:55:55.000Z" title="发表于 2024-01-31 14:55:55">2024-01-31</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2023 - 2024 By 十一星野</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">简</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.staticfile.org/fancyapps-ui/5.0.32/fancybox/fancybox.umd.min.js"></script><script src="https://cdn.staticfile.org/instant.page/5.2.0/instantpage.min.js" type="module"></script><div class="js-pjax"></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div><div id="local-search-stats-wrap"></div></div></div><div id="search-mask"></div><script src="/js/search/local-search.js"></script></div></div></body></html>